/**
 * @file     dailyTemperatures.js
 * @brief    [739. 每日温度](https://leetcode.cn/problems/daily-temperatures/)
 * @author   Zhu
 * @date     2024-11-27 19:26
 */

/**
 * 暴力
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    const n = temperatures.length;
    const ans = [];

    for (let i = 0; i < n; i++) {
        ans[i] = 0;
        let j = i + 1;
        while (j < n) {
            if (temperatures[i] < temperatures[j]) {
                ans[i] = j - i;
                break;
            }
            j++;
        }
    }
    return ans;
};

/**
 * 单调栈 O(n)
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
    const n = temperatures.length;
    const ans = [];
    const stack = [];
    const top = () => stack[stack.length - 1];

    for (let i = 0; i < n; i++) {
        ans[i] = 0;
        // 栈空时直接入栈，if(stack.length===0) { stack.push(i);continue; }
        // 栈顶有值，比较后决定出入栈
        while (stack.length > 0 && temperatures[i] > temperatures[top()]) {
            const j = stack.pop();
            ans[j] = i - j;
        }
        stack.push(i);
    }

    return ans;
};
